%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Masters/Doctoral Thesis 
% LaTeX Template
% Version 1.41 (9/9/13)
%
% This template has been downloaded from:
% http://www.latextemplates.com
%
% Original authors:
% Steven Gunn 
% http://users.ecs.soton.ac.uk/srg/softwaretools/document/templates/
% and
% Sunil Patel
% http://www.sunilpatel.co.uk/thesis-template/
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
% Note:
% Make sure to edit document variables in the Thesis.cls file
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------

\documentclass[11pt, a4paper, oneside]{Thesis} % Paper size, default font size and one-sided paper
% \documentclass{Thesis}
\graphicspath{{Pictures/}} % Specifies the directory where pictures are stored

\usepackage{float}[2001/11/08]%    v1.3d
\usepackage{placeins}[2005/04/18]% v2.2  ; for \FloatBarrier
\usepackage{rotating}[2009/03/28]% v2.16a; for sidewaystable-environment
\usepackage{hyperref}[2012/11/06]% v6.83m

% \usepackage{tablefootnote}[2014/01/26]%   v1.1c
\usepackage[square, comma, sort&compress]{natbib} % Use the natbib reference package - read up on this to edit the reference style; if you want text (e.g. Smith et al., 2012) for the in-text references (instead of numbers), remove 'numbers' 
\hypersetup{urlcolor=blue, colorlinks=true} % Colors hyperlinks in blue - change to black if annoying
\title{\ttitle} % Defines the thesis title - don't touch this

\begin{document}

\frontmatter % Use roman page numbering style (i, ii, iii, iv...) for the pre-content pages

\setstretch{1.3} % Line spacing of 1.3

% Define the page headers using the FancyHdr package and set up for one-sided printing
\fancyhead{} % Clears all page headers and footers
\cfoot{\thepage} % Sets the right side header to show the page number
% \lhead{} % Clears the left side page header

\pagestyle{fancy} % Finally, use the "fancy" page style to implement the FancyHdr headers

\newcommand{\HRule}{\rule{\linewidth}{0.5mm}} % New command to make the lines in the title page

% PDF meta-data
\hypersetup{pdftitle={\ttitle}}
\hypersetup{pdfsubject=\subjectname}
\hypersetup{pdfauthor=\authornames}
\hypersetup{pdfkeywords=\keywordnames}

%----------------------------------------------------------------------------------------
%	TITLE PAGE
%----------------------------------------------------------------------------------------

% \begin{titlepage}
\pagestyle{empty}
\begin{center}

\vspace*{6ex}
{\huge \bfseries Implementing and Accelerating\\ HMMER3 Protein Sequence Search on CUDA-Enabled GPU}\\[4cm] % Thesis title
 
\textsc {\Large \href{http://ca.linkedin.com/pub/lin-cheng/19/191/422} \authornames}\\[3cm] % Thesis type

\large \textsc{A thesis\\ in\\ The Department\\ of\\ \deptname }\\[3cm] % University requirement text
{Presented in Partial Fulfilment of the Requirements\\ For the Degree of \degreename \\ \univname\\ Montr\'{e}al, Qu\'{e}bec, Canada}\\[1cm]
 
{\large \today}\\ % Date
{\textcopyright \authornames, 2014}
%\includegraphics{Logo} % University/department logo - uncomment to place it
 
\vfill
\end{center}

% \end{titlepage}

\clearpage

\pagestyle{empty} % No headers or footers for the following pages
  \vspace{1em}
%     \vspace{1ex}
     \begin{center}
        CONCORDIA UNIVERSITY
     \end{center}
     \begin{center}
        School of Graduate Studies
     \end{center}
     \vspace{3ex}
     This is to certify that the thesis prepared\\[2ex]
     By :\hspace{38pt}{\bf {\authornames}}\\[2ex]
     Entitled :\hspace*{13pt}{\bf \ttitle}\\[2ex] 
    and submitted in partial fulfilment of the requirements for the degree
    of\\[2ex]
    \hspace*{62pt}{\bf \degreename}\\[2ex]
    complies with the regulations of this University and meets the accepted
    standards with respect to originality and quality. \\[2ex]
    Signed by the final examining committee : \\[5ex]
    \hspace*{77pt}\underline{\hspace{234pt}} Chair\\
    \hspace*{77pt}Dr.\@ Brigitte Jaumard \\[2.5ex]
    \hspace*{77pt}\underline{\hspace{234pt}} Examiner\\
    \hspace*{77pt}Dr.\@ Dhrubajyoti Goswami \\[2.5ex]
    \hspace*{77pt}\underline{\hspace{234pt}} Examiner\\
    \hspace*{77pt}Dr.\@ Hovhannes A. Harutyunyan \\[2.5ex]
    \hspace*{77pt}\underline{\hspace{234pt}} Supervisor \\
    \hspace*{77pt}\@ \supname\\[2.5ex]
    Approved by \hspace{9pt}\underline{\hspace{232pt}}\\
    \hspace*{79pt}Chair of Department or Graduate Program Director\\[6ex]
    \underline{\hspace*{100pt}} \hspace{10pt}  2014. \hspace{48pt} \underline{\hspace{200pt}}\\
    \hspace*{200pt}Dr.\@ Robin A. L. Drew \\
    \hspace*{200pt}Dean of Faculty\\    
    \hspace*{200pt}(\deptname)

\clearpage

%----------------------------------------------------------------------------------------
%	ABSTRACT PAGE
%----------------------------------------------------------------------------------------

% \addtotoc{Abstract} % Add the "Abstract" page entry to the Contents

%   \thispagestyle{empty}
%   \null\vfil
%   \begin{center}
%     \setlength{\parskip}{0pt}
%     \bigskip
%     {\huge{\textit{Abstract}} \par}
%     \bigskip
%     \bigskip
%     {\normalsize\bf \@title \par} % Thesis title
%     \medskip
%     {\normalsize \authornames \par} % Author name
%     \bigskip
%   \end{center}
\pagestyle{fancy}
\abstract{{\vspace{1em}} % Add a gap in the Contents, for aesthetics

The recent emergence of multi-core CPU and many-core GPU architectures has made parallel computing more accessible. Hundreds of industrial and research applications have been mapped onto GPUs to further utilize the extra computing resource.
In bioinformatics, HMMER is a set of widely used applications for sequence analysis based on Hidden Markov Model. One of the tools in HMMER, \emph{hmmsearch}, and the Smith-Waterman algorithm are two important tools for protein sequence analysis that use dynamic programming. Both tools are particularly well-suited for many-core GPU architecture due to the parallel nature of sequence database searches. 

After studying the existing research on CUDA acceleration in bioinformatics, this thesis investigated the acceleration of the key Multiple Segment Viterbi algorithm in HMMER version 3. A fully-featured CUDA-enabled protein database search tool \emph{cudaHmmsearch} was designed, implemented and optimized. We demonstrated a variety of optimization strategies that are useful for general purpose GPU-based applications. Based on our optimization experience in parallel computing, six steps were summarized for optimizing performance using CUDA programming. 

We made comprehensive tests and analysis for multiple enhancements in our GPU kernels in order to demonstrate the effectiveness of selected approaches. The performance analysis showed that GPUs are able to deal with intensive computations, but are very sensitive to random accesses to the global memory. The results show that our implementation achieved 2.5x speedup over the single-threaded HMMER3 CPU SSE2 implementation on average.

}
\clearpage % Start a new page

%----------------------------------------------------------------------------------------
%	ACKNOWLEDGEMENTS
%----------------------------------------------------------------------------------------

\setstretch{1.3} % Reset the line-spacing to 1.3 for body text (if it has changed)

% \acknowledgements{\addtocontents{toc}{\vspace{1em}} % Add a gap in the Contents, for aesthetics
\acknowledgements{{\vspace{1em}} % Add a gap in the Contents, for aesthetics

First, I am truely thankful to my supervisor {\supname} for his profound knowledge, flexibility in supervising students, warm-hearted, and selecting this interesting topic for my research.

I also give thanks to my friendly group: Faizah Aplop, Christine Houry Kehyayan, Nada Alhirabi, Asma Mistadi and Qing Ye for their communicating and helping me know more about Bioinformatics and life in Montreal, Stuart Thiel for providing Kronos machine as my developing and benchmarking environment.

My deepest gratitude goes to my family in China for their unquestioning love. I miss them so much in Canada. Hope less visa trouble between the two countries I love.

}
\clearpage % Start a new page

%----------------------------------------------------------------------------------------
%	LIST OF CONTENTS/FIGURES/TABLES PAGES
%----------------------------------------------------------------------------------------

\thispagestyle{plain} % The page style headers have been "empty" all this time, now use the "fancy" headers as defined before to bring them back

% \lhead{\emph{Contents}} % Set the left side page header to "Contents"
\tableofcontents % Write out the Table of Contents

% \lhead{\emph{List of Figures}} % Set the left side page header to "List of Figures"
\listoffigures % Write out the List of Figures

\lhead{\emph{List of Tables}} % Set the left side page header to "List of Tables"
\listoftables % Write out the List of Tables

%----------------------------------------------------------------------------------------
%	ABBREVIATIONS
%----------------------------------------------------------------------------------------

\clearpage % Start a new page

\setstretch{1.5} % Set the line spacing to 1.5, this makes the following tables easier to read

\lhead{\emph{Abbreviations}} % Set the left side page header to "Abbreviations"
\listofsymbols{ll} % Include a list of Abbreviations (a table of two columns)
{
\textbf{CUDA} & \textbf{C}ompute \textbf{U}nified \textbf{D}evice \textbf{A}rchitecture \\
\textbf{DMA} & \textbf{D}irect \textbf{M}emory \textbf{A}ccess \\
\textbf{DP} & \textbf{D}ynamic \textbf{P}rogramming \\
\textbf{GPU} & \textbf{G}raphics \textbf{P}rocessing \textbf{U}nit \\
\textbf{HMM} & \textbf{H}idden \textbf{M}arkov \textbf{M}odel \\
\textbf{HMMER} & \textbf{H}idden \textbf{M}arkov \textbf{M}odel\textbf{ER} \\
\textbf{MPI} & \textbf{M}essage \textbf{P}assing \textbf{I}nterface \\
\textbf{MSV} & \textbf{M}ultiple \textbf{S}egment \textbf{V}iterbi \\
\textbf{NCBI} & \textbf{N}ational \textbf{C}enter for \textbf{B}iotechnology \textbf{I}nformation) \\
\textbf{NR} & \textbf{N}on-\textbf{R}edundant \\
\textbf{OS} & \textbf{O}perating \textbf{S}ystem \\
\textbf{Pfam} & \textbf{P}rotein \textbf{fam}ilies \\
\textbf{SIMD} & \textbf{S}ingle-\textbf{I}nstruction \textbf{M}ultiple-\textbf{D}ata \\
\textbf{SM} & \textbf{S}treaming \textbf{M}ultiprocessors \\
\textbf{SSE} & \textbf{S}treaming \textbf{S}IMD \textbf{E}xtensions \\
\textbf{SW} & \textbf{S}mith-\textbf{W}aterman
% \textbf{LAH} & \textbf{L}ist \textbf{A}bbreviations \textbf{H}ere \\
% \textbf{Acronym} & \textbf{W}hat (it) \textbf{S}tands \textbf{F}or \\
}

%----------------------------------------------------------------------------------------
%	PHYSICAL CONSTANTS/OTHER DEFINITIONS
%----------------------------------------------------------------------------------------

% \clearpage % Start a new page
% 
% \lhead{\emph{Physical Constants}} % Set the left side page header to "Physical Constants"
% 
% \listofconstants{lrcl} % Include a list of Physical Constants (a four column table)
% {
% Speed of Light & $c$ & $=$ & $2.997\ 924\ 58\times10^{8}\ \mbox{ms}^{-\mbox{s}}$ (exact)\\
% % Constant Name & Symbol & = & Constant Value (with units) \\
% }

%----------------------------------------------------------------------------------------
%	SYMBOLS
%----------------------------------------------------------------------------------------

% \clearpage % Start a new page
% 
% \lhead{\emph{Symbols}} % Set the left side page header to "Symbols"
% 
% \listofnomenclature{lll} % Include a list of Symbols (a three column table)
% {
% $a$ & distance & m \\
% $P$ & power & W (Js$^{-1}$) \\
% % Symbol & Name & Unit \\
% 
% & & \\ % Gap to separate the Roman symbols from the Greek
% 
% $\omega$ & angular frequency & rads$^{-1}$ \\
% % Symbol & Name & Unit \\
% }

%----------------------------------------------------------------------------------------
%	DEDICATION
%----------------------------------------------------------------------------------------

% \setstretch{1.3} % Return the line spacing back to 1.3
% 
% \pagestyle{empty} % Page style needs to be empty for this page
% 
% \dedicatory{For/Dedicated to/To my\ldots} % Dedication text
% 
% \addtocontents{toc}{\vspace{2em}} % Add a gap in the Contents, for aesthetics

%----------------------------------------------------------------------------------------
%	THESIS CONTENT - CHAPTERS
%----------------------------------------------------------------------------------------

\mainmatter % Begin numeric (1,2,3...) page numbering

\pagestyle{fancy} % Return the page headers back to the "fancy" style
\pagestyle{plain}
% Include the chapters of the thesis as separate files from the Chapters folder
% Uncomment the lines as you write the chapters

\input{Chapters/Intro}
\input{Chapters/Background}
% \input{Chapters/DynamicProg} 
% \input{Chapters/CUDASeqAlign}
\input{Chapters/CUDAHMMER3} 
\input{Chapters/Results} 
%\input{Chapters/Chapter6} 
%\input{Chapters/Chapter7} 

%----------------------------------------------------------------------------------------
%	THESIS CONTENT - APPENDICES
%----------------------------------------------------------------------------------------

\addtocontents{toc}{\vspace{2em}} % Add a gap in the Contents, for aesthetics

\appendix % Cue to tell LaTeX that the following 'chapters' are Appendices

% Include the appendices of the thesis as separate files from the Appendices folder
% Uncomment the lines as you write the Appendices

\input{Appendices/AppendixA}
%\input{Appendices/AppendixB}
%\input{Appendices/AppendixC}

\addtocontents{toc}{\vspace{2em}} % Add a gap in the Contents, for aesthetics

\backmatter

%----------------------------------------------------------------------------------------
%	BIBLIOGRAPHY
%----------------------------------------------------------------------------------------

\label{Bibliography}

\lhead{\emph{Bibliography}} % Change the page header to say "Bibliography"

\bibliographystyle{unsrtnat} % Use the "unsrtnat" BibTeX style for formatting the Bibliography

\bibliography{Bibliography} % The references (bibliography) information are stored in the file named "Bibliography.bib"

\end{document}  